#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (auto& it : nums)
        if (it <= 0)
            it = n + 1;

    for (int i = 0; i < n; i++)
    {
        int num = abs(nums[i]);
        if (num <= n)
            nums[num - 1] = -abs(nums[num - 1]);
    }

    for (int i = 0; i < n; i++)
        if (nums[i] > 0)
            return i + 1;
    return n + 1;
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<int> q(n);
    vector<bool> col(n), diag1(n * 2 - 1), diag2(n * 2 - 1);

    auto dfs = [&](auto&& dfs, int r) {
        if (r == n)
        {
            vector<string> t;
            for (int i = 0; i < n; i++)
                t.push_back(string(q[i], '.') + 'Q' + string(n - 1 - q[i], '.'));
            res.push_back(t);
            return;
        }

        for (int c = 0; c < n; c++)
        {
            int rc = r - c + n - 1;
            if (!col[c] && !diag1[r + c] && !diag2[rc])
            {
                q[r] = c;
                col[c] = diag1[r + c] = diag2[rc] = true;
                dfs(dfs, r + 1);
                col[c] = diag1[r + c] = diag2[rc] = false;
            }
        }
    };

    dfs(dfs, 0);
    return res;
}